package top.humbleyuan.linkedlist;

import top.humbleyuan.datastructure.linkedlist.LinkNode;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author HumbleYuan
 * @Date 2020/5/18 22:20
 * @Des 返回环形链表的环的第一个节点
 * @pro 待补充双指针(佛洛依德环)
 */
public class LeetCode_142 {
    public static void main(String[] args) {
        // 哈希
        m1();
    }

    public static void m1() {
        /**
         * 数据准备
         */
        LinkNode head = new LinkNode(3);
        int[] vals = {};

        //末尾与第几个点结成环
        int ringIndex = 0;
        head = LinkNode.formLink(head,vals,ringIndex);


        LinkNode temp = head;
        Map<LinkNode,Integer> linkNodeHashMap = new HashMap<>();

        int index = 0;
        while(temp != null) {
            if(linkNodeHashMap.containsKey(temp)) {
                System.out.println("有环,index:" + linkNodeHashMap.get(temp));
                return;
            }

            linkNodeHashMap.put(temp,index ++);
            temp = temp.next;
        }


        System.out.println("无环");
    }
}
